class Solution {
private:
    vector<vector<int>> list1;
    vector<int> inDegree;
public:
//思路一：要证明是否能全部上完课，就要证明判断是不是拓扑结构，有没有环。抓住每个结点的出度入度特征。
/*
    本题使用广度遍历的策略，用队列存储所有入度为0的结点，不断更行 结点的入度，最后判断是否能够遍历所有节点
    用队列来实现拓扑结构
*/
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        list1.resize(numCourses);
        inDegree.resize(numCourses);
        //邻接表 表示每个结点的后续节点
        for(int i=0;i<prerequisites.size();i++){
            list1[prerequisites[i][1]].push_back(prerequisites[i][0]);
            //每个结点的入度记录
            inDegree[prerequisites[i][0]]++;
        }

        queue<int> queueTemp;
        //先放入入度为0的结点
        for (int i=0;i<numCourses;++i) {
            if (inDegree[i]==0) {
                queueTemp.push(i);
            }
        }
        int visited=0;
        //在遍历的时候会把所有入度为0的结点放入队列，当有换的情况下，无法遍历所有结点
        while(!queueTemp.empty()){
            visited++;
            int k=queueTemp.front();
            queueTemp.pop();
            for(int x:list1[k]){
                inDegree[x]--;
                if(inDegree[x]==0){
                    queueTemp.push(x);
                }
            }
        }
        if(visited==numCourses){
            return true;
        }
        return false;
    }
};